/*
 * @Author: szx
 * @Date: 2021-12-29 13:45:18
 * @LastEditTime: 2021-12-30 14:48:32
 * @Description:
 * @FilePath: \leetcode\1-99\51\51.js
 */
/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
    const res = [];
    const backtrack = (path, row) => {
        if (row == n) {
            let arr = [];
            path.forEach((row) => {
                arr.push(row.join(''));
            });
            res.push(arr.slice());
            return;
        }
        for (let col = 0; col < n; col++) {
            if (!isValid(path, row, col)) continue;
            path[row][col] = 'Q';
            backtrack(path, row + 1);
            path[row][col] = '.';
        }
    };
    const isValid = (path, row, col) => {
        for (let i = 0; i < row; i++) {
            if (path[i][col] == 'Q') {
                return false;
            }
        }
        for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (path[i][j] == 'Q') {
                return false;
            }
        }
        for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (path[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    };
    backtrack(
        new Array(n).fill('.').map(() => new Array(n).fill('.')),
        0
    );
    return res;
};
console.log(solveNQueens(4));
